package org.bigmarketapi.projectreview.PrefixTree;


import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * @BelongsProject: API-GateWay
 * @BelongsPackage: org.bigmarketapi.apigateway.Session.PrefixTree
 * @Author: dujiaqi
 * @CreateTime: 2024-11-27  22:45
 * @Description: TODO
 * @Version: 1.0
 */
@Slf4j
public class URLSearch {
    /**
     * @description: 利用DFS与回溯进行查找
     * @author: dujiaqi
     * @date: 2024/11/27 22:50
     * @param: [treeNode, prefix]
     * @return: org.bigmarketapi.apigateway.Session.PrefixTree.TreeNode
     **/
    public static TreeNode findNodeWithPrefix(TreeNode node, String prefix) {
        //DFS进行精准判断，若出现错误则退回，进行回溯
        if (node == null) {
            throw new RuntimeException("节点为NULL");
        }
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        //首先将根节点Root进行入栈
        stack.push(new Pair<>(node, 0));
        while (!stack.isEmpty()) {
            //进行DFS深度搜索遍历
            final Pair<TreeNode, Integer> top = stack.peek();
            final TreeNode treeNode = top.getKey();
            Integer childIndex = top.getValue();
            log.info("treeNode: {},childIndex: {}", treeNode.getPathSegment(), childIndex);
            //获取某个节点的总路径（从当前一直循环遍历）
            final String fullPath = constructFullPath(treeNode);
            log.info("fullPath: {}", fullPath);
            if (prefixMatch(fullPath, prefix)) {
                return treeNode;
            }
            if (childIndex >= treeNode.getChildren().size()) {
                //进行回溯：退至上一步然后DFS继续进行搜索
                final Pair<TreeNode, Integer> pop = stack.pop();
                log.info("pop: {}", pop.getKey().getPathSegment());
            } else {
                stack.push(new Pair<>(treeNode.getChildren().get(childIndex), 0));
                top.setValue(childIndex + 1);
                log.info("top- path:{}, value:{}", top.getKey().getPathSegment(), top.getValue());
            }
        }
        return null;
    }

    public static boolean prefixMatch(String pathSegment, String prefix) {
        return pathSegment.startsWith(prefix);
    }

    public static String constructFullPath(TreeNode node) {
        StringBuilder fullPath = new StringBuilder();
        while (node.getParent() != null) {
            fullPath.insert(0, "/" + node.getPathSegment());
            node = node.getParent();
        }
        fullPath.insert(0, node.getPathSegment());
        return fullPath.toString();
    }
}
